package 数组和链表;

import leetcode.editor.cn.MergeListNode;
import 抽象数据类型.ListNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @description:
 * @author: ywk
 * @date: 2020-10-29
 */
public class 合并k个已排序的链表 {
    public static void main(String[] args) {
        ListNode l1 = null;
        ListNode l2 = null;
        ListNode l3 = null;
        l3 = MergeListNode.proList(new int[]{-3, -1, 2, 9}, 0, l3);
        l1 = MergeListNode.proList(new int[]{-3, -1, 2, 9}, 0, l1);
        l2 = MergeListNode.proList(new int[]{-3, -1, 2, 9}, 0, l2);
        ArrayList<ListNode> lists = new ArrayList<>();
        lists.add(l1);
        lists.add(l2);
        lists.add(l3);
        MergeListNode.prtList(mergeKLists(lists));
    }

    public ListNode mergeKListss(ArrayList<ListNode> lists) {
        List<Integer> list = new ArrayList<>();
        for (ListNode listNode : lists) {
            ListNode root = listNode;
            while (root != null) {
                list.add(root.val);
                root = root.next;
            }
        }
        Collections.sort(list);
        ListNode head = new ListNode(Integer.MAX_VALUE);
        ListNode next = head;
        for (int i = 0; i < list.size(); i++) {
            next.next = new ListNode(list.get(i));
            next = next.next;
        }
        return head.next;
    }

    public static ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        return mergeKLists(lists, 0, lists.size() - 1);
    }

    public static ListNode mergeKLists(ArrayList<ListNode> lists, int start, int end) {
        if (start < end) {
            int mid =  (start + end) / 2;
            ListNode l1 = mergeKLists(lists, start, mid);
            ListNode l2 = mergeKLists(lists, mid + 1, end);
            return merge(l1, l2);
        }
        return lists.get(start);
    }


    private static ListNode merge(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head = new ListNode(Integer.MAX_VALUE);
        ListNode next = head;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                next.next = l2;
                l2 = l2.next;
                next = next.next;
            } else {
                next.next = l1;
                l1 = l1.next;
                next = next.next;
            }
            if (l1 == null) {
                next.next = l2;
                break;
            }
            if (l2 == null) {
                next.next = l1;
                break;
            }
        }
        return head.next;
    }
}